#include <queue>
#include <functional>
#include <iostream>
#include <queue>


#include "unionfind/UnionFind.h"
#include "GraphAlgorithm.h"

#define MAX_DIST    10000
#define VAILD_V     -1

using namespace std;

//连通图的广度优先遍历：类似于树的层序遍历
vector<int> GraphAlgorithm::BFS(Graph *graph, int v) {
    queue<int> q;
    vector<bool> visited(graph->V(), false);
    vector<int> ret;
    q.push(v);
    visited[v] = true;
    while (!q.empty()) {
        int s = q.front();
        ret.push_back(s);
        vector<int> l = graph->Adj(s);
        for (auto &r : l) {
            if (!visited[r]) {
                q.push(r);
                visited[r] = true;
            }
        }
        q.pop();
    }
    return ret;
}

//TODO:非连通图的广度优先遍历：对所有节点调用BFS

//连通图的深度优先遍历：类似于树的先序遍历
vector<int> GraphAlgorithm::DFS(Graph *graph, int v) {
    vector<bool> visited(graph->V(), false);
    vector<int> ret;

    std::function<void(int v)> f;
    f = [&, graph](int v) {
        vector<int> l = graph->Adj(v);
        for (auto &r : l) {
            if (!visited[r]) {
                //注意：先标记再去访问相邻节点
                visited[r] = true;
                ret.push_back(r);
                f(r);
            }
        }
    };

    visited[v] = true;
    ret.push_back(v);

    f(v);

    return ret;
}

//每次加入到图A中的安全边永远都是连接A和A之外某个结点的边中权重最小的边
//TODO:改进：即时删除
void GraphAlgorithm::MST_Prim(Graph *graph) {
    struct cmp {
        bool operator()(const Edge& E1, const Edge& E2) {
            return E1.w > E2.w;
        }
    };
    priority_queue<Edge, vector<Edge>, cmp> Q;
    vector<bool> marked(graph->V(), false);
    vector<Edge> mst;

    auto visit = [&](int curv) {
        vector<int> adj = graph->Adj(curv);
        for (const auto &v : adj) {
            if (marked[v])
                continue;
            Q.push(Edge{curv, v, graph->Weight(curv, v)});
        }
    };

    int curV = 0;
    visit(curV);
    marked[curV] = true;
    while (!Q.empty()) {
        auto e = Q.top();
        Q.pop();
        if (marked[e.v1] && marked[e.v2]) {
            //如果边e的两个顶点全都已经被加入到最小生成树中
            //边e直接被弹出
            continue;
        }
        mst.push_back(e);
        if (marked[e.v1]) {
            marked[e.v2] = true;
            visit(e.v2);
        } else {
            marked[e.v1] = true;
            visit(e.v1);
        }
    }

    for (auto &r : mst) {
        cout << "v1 = " << r.v1 << " v2 = " << r.v2 << " w = " << graph->Weight(r.v1, r.v2) << endl;
    }
    cout << endl;

}

//在所有连接森林中两棵不同树的边里面，找到权重最小的边 (u, v) 作为安全边
void GraphAlgorithm::MST_Ksuskal(Graph *graph) {
	struct cmp {
        bool operator()(const Edge& E1, const Edge& E2) {
            return E1.w > E2.w;
        }
    };

    priority_queue<Edge, vector<Edge>, cmp> Q;
	const vector<Edge> &allEdge = graph->getAllEdge();
	for (auto &e : allEdge) {
		Q.push(e);
	}
	vector<Edge> mst;
    vector<bool> marked(graph->V(), false);
    UnionFind uf(graph->V());
	while (!Q.empty()) {
		const Edge &e = Q.top();
		if (uf.find(e.v1) == uf.find(e.v2)) {
			Q.pop();
			continue;
		}
		mst.push_back(e);
        uf.add(uf.find(e.v1), uf.find(e.v2));
		Q.pop();
	}
	
	for (auto &r : mst) {
        cout << "v1 = " << r.v1 << " v2 = " << r.v2 << " w = " << graph->Weight(r.v1, r.v2) << endl;
    }
    cout << endl;
}


//单点最短路径：从一个端点到另一个端点的成本最小路径
void GraphAlgorithm::SP_BellmanFord(Graph *graph) {
    
}

//TODO:优化
int selectMin(vector<int> arr, vecotr<bool> marked) {
    int min = -1;
    int index = -1;
    for (int i = 0; i < arr.size(); i++) {
        if (!marked[i] && min > arr[i]) {
            min = arr[i];
            index = i;
        }
    }
    return index;
}

//TODO:优化
bool isDijkstraFinish(vector<int> distto, vector<bool> marked) {
    for (int i = 0; i < distto.size(); i++) {
        if (!marked[i] && distto[i] < MAX_DIST)
            return false;
    }
    return true;
}

//Dijkstra算法：
//首先将distto[0]初始化为0，distto[]中其他元素为正无穷，
//每次从distto[]中选择最小的非树节点进行放松并加入树中，
//直到所有节点都加入树中，或者distto[]中所有非树节点的值都为正无穷
void GraphAlgorithm::SP_Dijkstra(Graph *graph) {
    vector<bool> marked(graph->V(), false);
    vector<int> distto(graph->V(), MAX_DIST);
    vector<int> edgeto(graph->V(), VAILD_V);

    int curr = 0;
    marked[0] = true;

    while (!isDijkstraFinish(distto, marked)) {
        int index = selectMin(distto, marked);
        relax(graph, index, distto, edgeto);
        marked[index] = true;
    }
}

//松弛v点
void GraphAlgorithm::relax(Graph *graph, int v, vector<int> &distto, vector<int>& edgeto) {
    vector<int> adj = graph->Adj(v);
    for (auto &r : adj) {
        if (distto[r] > distto[v] + graph->Weight(v, r)) {
            distto[r] = distto[v] + graph->Weight(v, r);
            edgeto[r] = v;
        }
    }
}